package algorithms.leaning.class05;

import common.util.MyUtil;

import java.util.Arrays;

/**
 * 快速排序3.0(随机快排+荷兰国旗技巧优化)
 * <p>
 * 在arr[L..R]范围上，进行快速排序的过程：
 * 1）在这个范围上，随机选一个数记为num，
 * 1）用num对该范围做partition，< num的数在左部分，== num的数中间，>num的数在右部分。假设== num的数所在范围是[a,b]
 * 2）对arr[L..a-1]进行快速排序(递归)
 * 3）对arr[b+1..R]进行快速排序(递归)
 * 因为每一次partition都会搞定一批数的位置且不会再变动，所以排序能完成
 *
 * @author guichang
 * @date 2021/5/31
 */

@SuppressWarnings("all")
public class Code3_快速排序_随机快排_递归 {

    public static void main(String[] args) {
        int[] array = MyUtil.createRandomArray(200, -500, 500);
        partition(array, 0, array.length - 1);
        MyUtil.print("排序后");
        MyUtil.print(Arrays.toString(array));
    }

    private static void partition(int[] array, int L, int R) {
        if (L >= R) {
            return;
        }
        // 从L到R中随机选出一个数跟R交换
        MyUtil.swap(array, (int) (Math.random() * (R - L + 1) + L), R);
        int[] newNums = partitionSub(array, L, R);
        // 双轴快排
        partition(array, L, newNums[0] - 1);
        partition(array, newNums[1] + 1, R);
    }

    private static int[] partitionSub(int[] array, int L, int R) {
        int index = L; // 遍历索引
        int less = L - 1; // 小于区起始位置
        int more = R; // 最后一个数提前加入大于区
        while (index < more) {
            if (array[index] < array[R]) {
                MyUtil.swap(array, index++, ++less);
            } else if (array[index] > array[R]) {
                MyUtil.swap(array, index, --more);
            } else {
                index++;
            }
        }
        MyUtil.swap(array, more, R);
        return new int[]{less + 1, more - 1};
    }

}